package com.leetcode.algorithm.y22.m07.w2;

/**
 * 430. 扁平化多级双向链表
 * 
 * https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/
 * 
 * @author jie.deng
 *
 */
public class Question0430Solution01 {

	public Node flatten(Node head) {
		if (head == null) {
			return head;
		}
		addNodes(head);
		return head;
	}

	private Node addNodes(Node cur) {
		if (cur.child == null && cur.next == null) {
			return cur;
		}
		if (cur.child == null) {
			return addNodes(cur.next);
		}
		if (cur.next == null) {
			Node child = cur.child;
			child.prev = cur;
			cur.child = null;
			cur.next = child;
			return addNodes(child);
		}

		Node next = cur.next;
		Node child = cur.child;

		// 建立 cur 和 cur.child 的关系，并返回尾节点tail(非空)
		cur.next = child;
		child.prev = cur;
		cur.child = null;
		Node tail = addNodes(child);

		// 建立 tail 和 next 的关系
		tail.next = next;
		next.prev = tail;

		return addNodes(next);
	}

}

class Node {
	public int val;
	public Node prev;
	public Node next;
	public Node child;
	public Node(int val, Node prev, Node next, Node child) {
		super();
		this.val = val;
		this.prev = prev;
		this.next = next;
		this.child = child;
	}
	
};